package _01_动态数组;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class _84_柱状图中最大的矩形 {

    public static void main(String[] args) {

        _84_柱状图中最大的矩形 v = new _84_柱状图中最大的矩形();

        int[] ins = new int[]{0, 1, 0, 2, 0, 3, 0};
        System.out.println(v.largestRectangleArea(ins));

    }

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] rightMin = new int[len];
        Arrays.fill(rightMin, -1);
        for (int i = len - 2; i >= 0; --i) {
            int position = i + 1;
            while (heights[position] >= heights[i]) {
                if (rightMin[position] == -1) {
                    position = -1;
                    break;
                } else {
                    position = rightMin[position];
                }
            }
            rightMin[i] = position;
        }
        int[] leftMin = new int[len];
        Arrays.fill(leftMin, -1);
        for (int i = 1; i < len; ++i) {
            int position = i - 1;
            while (heights[position] >= heights[i]) {
                if (leftMin[position] == -1) {
                    position = -1;
                    break;
                } else {
                    position = leftMin[position];
                }
            }
            leftMin[i] = position;
        }

        // 计算最大面积
        int area = 0;
        for (int i = 0; i < len; ++i) {
            int leftWidth = leftMin[i] == -1? i + 1: i - leftMin[i];
            int rightWidth = rightMin[i] == -1? len - i: rightMin[i] - i;
            area = Math.max(area, (rightWidth + leftWidth - 1) * heights[i]);
        }
        return area;
    }

}
